#include<bits/stdc++.h>
#define ll long long
template <typename T> inline void read(T &x) {
    x = 0; char ch = getchar(); int f = 1;
    while (!isdigit(ch) && ch ^ '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); x *= f;
}
using namespace std;
const int N=1e5+5,L=6e5+5,mo=1e9+7;
int n,T,A,B,nxt[N],lenA,lenB,lens,ans;
bool u[L];
string f[31],s;
char S[N];
map<int,int> mp1,mp2,mp3,mp4;
struct Mat
{
	int x,y;
	ll a[3][3];
}Ans,mA;
Mat multi(Mat A,Mat B)
{
	Mat C;
	C.x=A.x,C.y=B.y;
	memset(C.a,0,sizeof(C.a));
	for(int a=0;a<A.x;a++)
	{
		for(int b=0;b<A.y;b++)
		{
			for(int c=0;c<B.y;c++)
			{
				C.a[a][c]+=A.a[a][b]*B.a[b][c];
			}
		}
	}
	for(int a=0;a<C.x;a++)
	{
		for(int b=0;b<C.y;b++) C.a[a][b]%=mo;
	}
	return C;
}
Mat mat_ksm(Mat Ans,Mat A,int b)
{
	while(b>0)
	{
		if(b%2==1) Ans=multi(Ans,A);
		A=multi(A,A);
		b/=2;
	}
	return Ans;
}
int main()
{
	freopen("brotherhood.in","r",stdin);
	freopen("brotherhood.out","w",stdout);
    f[1]="0",f[2]="1";
    for(int a=3;a<=29;a++) f[a]=f[a-1]+f[a-2];
    for(int a=0;a<=29;a++) f[a]='#'+f[a];
    for(int a=0;a<=29;a++) mp1[a]=mp2[a]=mp3[a]=mp4[a]=-1;
    scanf("%d%d",&n,&T);
    while(T--)
    {
    	ans=0;
    	scanf("%s",S);
   	    s=S;
    	s='#'+s;
    	for(int a=1;a<=29;a++)
    	{
    		if(f[a].size()-1>=s.size()-1)
    		{
    			A=a;
    			break;
			}
		}
		A=max(A,2);
		if(n==1&&A==2)
		{
			if(s[1]=='0')
			{
				printf("1\n");
				continue;
			}
		}
		if(n<A)
		{
			printf("0\n");
			continue; 
		}
	//	cout<<A<<endl;
		nxt[1]=0;
		for(int a=2,p=0;a<s.size();a++)
		{
			while(s[a]!=s[p+1]&&p>0) p=nxt[p];
			if(s[a]==s[p+1]) p++;
			nxt[a]=p;
		}
		for(int a=1;a<f[A+3].size();a++) u[a]=0;
		for(int i=1,j=0;i<f[A+3].size();i++)
		{
			while(s[j+1]!=f[A+3][i]&&j>0) j=nxt[j];
			if(s[j+1]==f[A+3][i]) j++;
			if(j==s.size()-1) u[i-j+1]=1,j=nxt[j];
		}
		B=A-1;
		lenA=f[A].size()-1,lenB=f[B].size()-1,lens=s.size()-1;
		if(n<=A+3)
		{
			ans=0;
			int len;
			if(n==A) len=lenA;
			else if(n==A+1) len=lenA+lenB;
			else if(n==A+2) len=2*lenA+lenB;
			else len=3*lenA+2*lenB;
			for(int a=1;a+lens-1<=len;a++)
			{
				if(u[a]==1) ans++;
			}
			printf("%d\n",ans);
			continue;
		}
		Ans.x=1,Ans.y=2;
		memset(Ans.a,0,sizeof(Ans.a));
		Ans.a[0][0]=0,Ans.a[0][1]=1;
		mA.x=mA.y=2;
		memset(mA.a,0,sizeof(mA.a));
		mA.a[0][1]=mA.a[1][0]=mA.a[1][1]=1;
		int h,cnt=0;
		if(mp1[A]==-1) mp1[A]=mat_ksm(Ans,mA,n-A+1).a[0][0];
		h=mp1[A];
		for(int a=1;a+lens-1<=lenA;a++)
		{
			if(u[a]==1) cnt++;
		}
		ans=((ll)ans+(ll)cnt*h)%mo;
		if(mp2[A]==-1) mp2[A]=mat_ksm(Ans,mA,n-A).a[0][0];
		h=mp2[A];
		cnt=0;
		for(int a=1;a+lens-1<=lenA+lenB;a++)
		{
			if(a<=lenA&&a+lens-1>lenA&&u[a]==1) cnt++;
		}
		if(u[lenA+1]==1&&lenB==lens) cnt++;
		ans=((ll)ans+(ll)cnt*h)%mo;
		Ans.x=1,Ans.y=3;
		memset(Ans.a,0,sizeof(Ans.a));
		Ans.a[0][1]=Ans.a[0][2]=1;
		mA.x=mA.y=3;
		memset(mA.a,0,sizeof(mA.a));
		mA.a[0][0]=mA.a[0][1]=mA.a[1][0]=mA.a[2][1]=mA.a[2][2]=1;
		mA.a[1][1]=2;
		if(mp3[A]==-1)
		{
      		if((A+2)%2==n%2) mp3[A]=mat_ksm(Ans,mA,(n-(A+2))/2).a[0][0];
	    	else mp3[A]=mat_ksm(Ans,mA,(n-(A+2))/2).a[0][1];
		}
		h=mp3[A];
		cnt=0;
		for(int a=lenA+lenB+1;a+lens-1<=3*lenA+lenB;a++)
		{
			if(a<=2*lenA+lenB&&a+lens-1>2*lenA+lenB&&u[a]==1) cnt++;
		}
		ans=((ll)ans+(ll)cnt*h)%mo;
		Ans.a[0][0]=1;
		mA.a[2][0]=1;
		if(mp4[A]==-1)
		{
	    	if((A+2)%2==n%2) mp4[A]=mat_ksm(Ans,mA,(n-(A+2))/2).a[0][0];
	     	else mp4[A]=mat_ksm(Ans,mA,(n-(A+2))/2).a[0][1];
		}
		h=mp4[A];
		cnt=0;
		for(int a=lenA+1;a+lens-1<=2*lenA+lenB;a++)
		{
			if(a<=lenA+lenB&&a+lens-1>lenA+lenB&&u[a]==1) cnt++;
		}
		for(int a=1;a+lens-1<=2*lenA+lenB;a++)
		{
			if(a<=lenA&&a+lens-1>lenA+lenB&&u[a]==1) cnt++;
		}
		ans=((ll)ans+(ll)cnt*h)%mo;
		printf("%d\n",ans);
	}
}
